package 并查集;

/**
 * @author shy_black
 * @date 2019/4/22 18:06
 * @Description:
 * 维护一个rank数组，记录并查集的层数，以提高合并集合的效率
 *
 */
public class UnionFind_3 implements UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind_3(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0;i < size;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    @Override
    public int getSize() {
        return parent.length;
    }
    private int find(int p) {
        if(p < 0 && p >= parent.length)
            throw new IllegalArgumentException("非法下标");
        while(p != parent[p])
            p = parent[p];
        return p;
    }
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if(rank[pRoot] < rank[qRoot])
            parent[pRoot] = qRoot;
        else if(rank[pRoot] > rank[qRoot])
            parent[qRoot] = pRoot;
        else {
            parent[pRoot] = qRoot;
            rank[qRoot]  += 1;
        }

    }
}
